//https://leetcode.cn/problems/binary-tree-preorder-traversal/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

//计算树节点总数
int treeSize(struct TreeNode* root){
    if(root==NULL){
        return 0;
    }

    return treeSize(root->left)
    +treeSize(root->right)
    +1;
}


//基于递归对树进行前序遍历
void preTreeOrder(struct TreeNode* root,int* a, int* pi){
    //空节点无返回值
    if(root==NULL){
        return;
    }

    a[(*pi)++]=root->val;
    preTreeOrder(root->left,a,pi);
    preTreeOrder(root->right,a,pi);
}


//原函数
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=treeSize(root);//计算树的总节点个数

    int* a=(int*)malloc(sizeof(int)*(*returnSize));//输出数组地址
    int i=0;

    preTreeOrder(root,a,&i);
    return a;
}